The present invention relates to decoding techniques and, more particularly, to apparatus and methods for decoding using message-passing techniques.
Conventional communications systems commonly use channel coding to reduce data transmission errors. Commonly used channel codes include convolutional and block codes. Commonly used convolutional codes include tail-biting codes, zero-trailing codes, and convolutional turbo codes. Commonly used block codes include Reed-Solomon codes, BCH codes, block turbo codes, and low density parity check (LDPC) codes.
LDPC coding has recently been adopted for use in digital television (DTV) transmission. LDPC codes are linear codes obtained from sparse bipartite graphs including “variable” (or “message”) nodes and “check” nodes that are connected by “edges.” Such a graph representation may be represented as a matrix. In particular, for a graph with n variable nodes and r check nodes, a binary r×n matrix may be defined wherein a particular entry (i, j) is a “1” if and only if the ith check node is connected to the jth variable node. This matrix is referred to as a parity check matrix. An LDPC code is characterized by a sparse parity check matrix.
Conventional LDPC decoding techniques typically employ iterative “message passing” algorithms. Such algorithms generally involve a series of rounds in which values are passed from variable nodes to check nodes and from check nodes back to variable nodes. Values sent from a variable node typically are computed based on the current value of the variable node and values received from neighboring check nodes.
A subclass of message passing algorithms called belief propagation algorithms are commonly used for LDPC decoding. In these algorithms, messages passed between nodes represent probabilities. In particular, a message passed from a variable node j to a check node i represents the probability that the variable node j has a certain value given the observed value of the variable node j and the values passed to the variable node j in the prior round from check nodes connected to the variable node j other than the check node i. A message passed from the check node i to the variable node j represents the probability that the variable node j has a certain value given the messages passed to the check node i the previous round from variable nodes other than the variable node j.
U.S. Pat. No. 6,539,377 to Blanksby et al describes a block-parallel decoding algorithm using a set of interconnected processing nodes configured in the form of a probability dependency graph, e.g., a bipartite probability dependency graph including variable and check nodes. A single iteration of the decoding process may produce within the variable nodes an update estimate for every bit or symbol in a given block. The decoding process is initiated by sending to each check node connected to a variable node a function ƒ(Rxi) where Rxi is the received bit or symbol and ƒ( ) is a function determined at least in part by the code, such as a threshold function, a linear scaling function or an approximate exponential function. The decoding process includes calculation in parallel at each of the check nodes a function g( ), e.g., a parity check function, of the input from the variable nodes connected to that check node, and sending to the connected variable nodes the result of these check node computations. The decoding process further includes calculating in parallel at each of the variable nodes a function h( ), e.g., a majority or averaging function, of the input from the check nodes connected to that variable node, and sending to the connected check nodes the results of these variable node computations. The process may be terminated when all check nodes satisfy a constraint of the code or after a maximum number of iterations. The values of the variable nodes at termination represent an estimate of the transmitted bit or symbol. The set of interconnected processing nodes may be implemented using one or more programmable computation units, each of which may be configured to implement a node or set of nodes.